//输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 
//
// 
//
// 示例: 
//给定如下二叉树，以及目标和 sum = 22， 
//
//               5
//             / \
//            4   8
//           /   / \
//          11  13  4
//         /  \    / \
//        7    2  5   1
// 
//
// 返回: 
//
// [
//   [5,4,11,2],
//   [5,8,4,5]
//]
// 
//
// 
//
// 提示： 
//
// 
// 节点总数 <= 10000 
// 
//
// 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/ 
// Related Topics 树 深度优先搜索 
// 👍 70 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Java：二叉树中和为某一值的路径
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P剑指_offer_34_ErChaShuZhongHeWeiMouYiZhiDeLuJingLcof {
    public static void main(String[] args) {
        Solution solution = new P剑指_offer_34_ErChaShuZhongHeWeiMouYiZhiDeLuJingLcof().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<Integer>> list = new ArrayList<>();

        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            if (root == null) {
                return list;
            }
            List<Integer> subList = new ArrayList<>();
            traverse(root, sum, subList);
            return list;
        }

        private void traverse(TreeNode root, int sum, List<Integer> subList) {
            if (root == null) {
                return;
            }
            sum -= root.val;
            subList.add(root.val);
            if (root.left == null && root.right == null && sum == 0) {
                list.add(new ArrayList<>(subList));
                subList.remove(subList.size() - 1);
                return;
            }
            traverse(root.left, sum, subList);
            traverse(root.right, sum, subList);
            subList.remove(subList.size() - 1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}